package 二叉树;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 */
public class _150_逆波兰表达式求值 {
    /**
     * 数组模拟栈
     *https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/
     * @param tokens
     * @return
     */

    public int evalRPN1(String[] tokens) {
        int n = tokens.length;
        int[] stack = new int[(n + 1) / 2];
        int index = -1;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            switch (token) {
                case "+":
                    index--;
                    stack[index] += stack[index + 1];
                    break;
                case "-":
                    index--;
                    stack[index] -= stack[index + 1];
                    break;
                case "*":
                    index--;
                    stack[index] *= stack[index + 1];
                    break;
                case "/":
                    index--;
                    stack[index] /= stack[index + 1];
                    break;
                default:
                    index++;
                    stack[index] = Integer.parseInt(token);
            }
        }
        return stack[index];
    }

    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) return 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if ("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)) {
                Integer b2 = stack.pop();
                Integer b1 = stack.pop();
                switch (s) {
                    case "+": {
                        stack.push(b1 + b2);
                        break;
                    }
                    case "-": {
                        stack.push(b1 - b2);
                        break;
                    }
                    case "*": {
                        stack.push(b1 * b2);
                        break;
                    }
                    case "/": {
                        stack.push(b1 / b2);
                        break;
                    }
                }
            }else{
                int a = Integer.parseInt(s);
                stack.push(a);
            }
        }
        return stack.peek();
    }
}
